package lcr;

import java.util.Deque;
import java.util.LinkedList;

public class Test0028 {
}

class Solution0028_1 {
    public Node flatten(Node head) {
        Deque<Node> deque = new LinkedList<>();
        Node ans = head;
        while (head!=null){
            if (head.child!=null){
                if (head.next!=null) deque.offer(head.next);

                Node child = head.child;
                head.next= child;
                child.prev=head;

                head.child=null;
                head=child;
            }else if (head.next==null){
                if (deque.isEmpty()) break;

                Node last = deque.pollLast();
                head.next= last;
                last.prev=head;

                head=last;
            }else {
                head=head.next;
            }


        }

        return ans;
    }

    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    };
}
